COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00017 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex[106,phy]
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a67.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Standardizing a finite machine\hfill}

Let $P$ be a program for a {\it finite machine\/} $M$, i.e., a~machine
with devices $\langle$control, input, output$\rangle$. We transform $P$
into~$P'$ that simulates~$P$ but uses scan, eof, and noop as its only
input operations. For each state $i\in Q$, there are states~$i↓{\Lambda}$
and $i↓{\rm end}\in Q'$. Additionally, for each $a\in\Sigma$, $i↓a\in Q'$.

The simulation relation $\rho$ is a partial function
$$\eqalign{&\langle i↓{\Lambda},x,y\rangle\;\rho\;\langle i,x,y\rangle\cr
&\langle i↓a,x,y\rangle\;\rho\;\langle i,ax,y\rangle\cr
&\langle i↓e,\Lambda,y\rangle\;\rho\;\langle i,\Lambda,y\rangle\,.\cr}$$
If $Q↓{\alpha}=\{i\}$, then $Q'↓{\alpha}=\{i↓{\Lambda}\}$. For
$j\in Q↓{\omega}$, $j↓{\rm end}\in Q'↓{\omega}$.

\bigskip
$$\vcenter{\halign{\hfil$#$\hfil\qquad&\hfil$#$\hfil\qquad&$\hfil#\hfil$\cr
&\alpha&\langle i,u,\Lambda\rangle\cr
\noalign{\smallskip}
u&&\rho\cr
\noalign{\smallskip}
&\alpha'&\langle i↓{\Lambda},u,\Lambda\rangle\cr
\noalign{\bigskip\bigskip}
\langle j,\Lambda,v\rangle&\omega\cr
\noalign{\smallskip}
\rho&&v\cr
\noalign{\smallskip}
\langle j↓{\rm end},\Lambda,v\rangle&\omega'\cr}}$$

\bigskip
\noindent
The diagrams above show the beginning and end of the simulation. The other
components are these:

\bigskip
$$\vcenter{\offinterlineskip%
\halign{\hfil$#$\hfil\qquad&$\hfil#\hfil$\qquad&\hfil$#$\hfil\qquad
&$\hfil#\hfil$\qquad&\hfil$#$\hfil\cr
&&\langle i,ax,y\rangle\cr
\noalign{\medskip}
&\rho&&\rho\cr
\noalign{\medskip}
&&\langle i↓{\Lambda}→i↓a,{\rm scan}\;a,{\rm noop}\rangle\cr
\langle i↓{\Lambda},ax,y\rangle&&&&\langle i↓a,x,y\rangle\cr
\noalign{\bigskip\bigskip}
&&\langle i,\Lambda,y\rangle\cr
\noalign{\medskip}
&\rho&&\rho\cr
\noalign{\medskip}
&&\langle i↓{\Lambda}→i↓{\rm end},{\rm eof},{\rm noop}\cr
\langle i↓{\Lambda},\Lambda,y\rangle&&&&\langle i↓{\rm end},\Lambda,y\rangle\cr}}$$

\medskip
\noindent
for all $i\in Q$, $a\in\Sigma$.

\vfill\eject
Additionally, for each instruction in $P$, there is a simulating instruction
in~$P'$.

\bigskip
$$\vcenter{\offinterlineskip%
\halign{\hfil$#$\hfil\qquad&$\hfil#\hfil$\qquad&\hfil$#$\hfil\cr
&\langle i→j,{\rm next}\; a,{\rm write}\; b\rangle\cr
\langle i,ax,y\rangle&&\langle j,ax,yb\rangle\cr
\noalign{\smallskip}
\rho &&\rho\cr
\noalign{\smallskip}
&\langle i↓a→j↓a,{\rm noop},{\rm write}\; b\rangle\cr
\langle i↓a,x,y\rangle&&\langle j↓a,x,yb\rangle\cr
\noalign{\bigskip\bigskip}
&\langle i→j,{\rm scan}\;a,{\rm write}\;b\rangle\cr
\langle i,ax,y\rangle&&\langle j,x,yb\rangle\cr
\noalign{\smallskip}
\rho&& \rho\cr
\noalign{\smallskip}
&\langle i↓a→j↓{\Lambda},{\rm noop},{\rm write}\;b\rangle\cr
\langle i↓a,x,y\rangle&&\langle j↓{\Lambda},x,yb\rangle\cr
\noalign{\bigskip\bigskip}
&\langle i→j,{\rm eof},{\rm write}\;b\rangle\cr
\langle i,\Lambda,y\rangle&&\langle j,\Lambda,yb\rangle\cr
\noalign{\smallskip}
 \rho&&\rho\cr
\noalign{\smallskip}
&\langle i↓{\rm end}→j↓{\rm end},{\rm noop},{\rm write}\;b\rangle\cr
\langle i↓{\rm end},\Lambda,y\rangle&&\langle j↓{\rm end},\Lambda,yb\rangle\cr
\noalign{\bigskip\bigskip}
&\langle i→j,{\rm noop},{\rm write}\;b\rangle\cr
\langle i,ax,y\rangle&&\langle j,ax,yb\rangle\cr
\noalign{\smallskip}
\rho&&\rho\cr
\noalign{\smallskip}
&\langle i↓a→j↓a,{\rm noop},{\rm write}\;b\rangle\cr
\langle i↓a,x,y\rangle&&\langle j↓a,x,yb\rangle\cr
\noalign{\bigskip\bigskip}
&\langle i→j,{\rm noop},{\rm write}\;b\rangle\cr
\langle i,\Lambda,y\rangle&&\langle j↓a,x,yb\rangle\cr
\noalign{\smallskip}
\noalign{\bigskip}
\noalign{\smallskip}
&\langle i↓{\rm end}→j↓{\rm end},{\rm noop},{\rm write}\;b\rangle\cr
\langle i↓{\rm end},\Lambda,y\rangle&&\langle j↓{\rm end},\Lambda,yb\rangle\cr}}$$

\noindent
where $b\in\Delta↑{\ast}$, write $\Lambda$ is the same as noop. Every instruction
of~$P$ can be simulated by one or two of~$P'$.

By inspecting the instructions of $P'$, one sees:

\smallskip
\display 20pt:$\bullet$:
End states lead only to end states.

\smallskip
\display 20pt:$\bullet$:
Instructions that go from non-end states to end states are the same as those
that execute eof.

\smallskip
\display 20pt:$\bullet$:
Initial states are not end states.

\smallskip
\display 20pt:$\bullet$:
Terminal states are end states.

\smallskip
\display 20pt:$\bullet$:
End states use only noop as the input operation.

\smallskip
\display 20pt:$\bullet$:
Eof, scan, and noop are the only input operations.

\smallskip
\display 20pt:$\bullet$:
Every instruction has a noop as its input operation, its output operation,
or both.

\smallskip
We conclude that any path through $P$ contains as its non-trivial input
operations a sequence of scans followed by an eof. Therefore every path is
executable, with uniquely defined input and output strings. If each arc in the
graph of the program is given a unique label, a~regular expression may be
constructed (Kleene's theorem) for the set of executable paths. By substituting
for the labels the characters scanned or~$\Lambda$s, one gets a regular
expression for the strings accepted. Similarly, one constructs a regular
expression for the strings written by accepting computations, and for the
traces of accepting computations.

Clearly a control state may occur in an accepting computation only if it lies
on a path from an initial state to an accepting state in the control graph.
All other states can be replaced by rejecting halts. If $\phi$ is the arc
relation in the control graph, one can construct $\phi↑{\ast}$ and test,
for each control state~$i$, whether $Q↓{\alpha}\,\phi↑{\ast}\,i$ and
whether $i\,\phi↑{\ast}\,Q↓{\omega}$. Unreachable states, in fact, can be
omitted from~$Q$.

A rejecting state $i$ that is not an end state may be reached without
consuming all input. We can make it consume all input by adding
$\langle i→i,{\rm scan}\;a,{\rm noop}\rangle$ for each $a\in\Sigma$,
and $\langle i→j,{\rm eof},{\rm noop}\rangle$, where the new state~$j$
is now the rejecting state.

Noops may be eliminated one at a time. If control state~$i$ is a noop state
(i.e., there is an instruction $\langle i→j,{\rm noop},{\rm noop}\rangle$)
then any instruction that goes to~$i$ could go directly to~$j$ instead.
If $i$ is initial, let $j$ be initial instead. Then omit $i$ and the noop
instruction. (If $j$ were equal to~$i$, state~$i$ would already have been
eliminated for never reaching a terminal state.)

After elimination of the noops, every nonterminal state~$i$ has one of two forms:

\bigskip
$$\vcenter{\halign{$\hfil#\hfil$\qquad&$\hfil#\hfil$\qquad\qquad\qquad\qquad\qquad
&$\hfil#\hfil$\qquad&$\hfil#\hfil$\qquad\cr
&&&{\rm write}\;b\cr
&{\rm scan}\;a↓1&i\cr
\noalign{\bigskip}
&{\rm scan}\;a↓2\cr
i\cr
&{\rm eof}\cr}}$$

\bigskip
\bigskip
\bigskip\noindent
If the original machine was a finite acceptor (i.e., did no writing), so is
the transformed machine, and every nonterminal state has the first form.
Then eofs lead only to terminal states.

The standardized machine always halts. It can not do as many as $|Q|$
consecutive writes (why?), and on input~$u$ can not do more than
$|u|+1$ input operations. This also shows that output length is bounded
by a linear function of input length.

\vfill\eject

$$\vcenter{\halign{\hfil#\hfil\quad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\cr
&&4&&&&&scan $b$\cr
&&\phantom{4000}$+$\cr
\noalign{\bigskip}
&&&scan $a$&&&&eof\cr
$\Rightarrow$&1&&&&&2&&5\cr
&&&&&&&&\phantom{5000}$-$\cr
&&scan $b$&&scan $b$\cr
&&&&&scan $a$\cr
&scan $a$\cr
&&&3\cr
\noalign{\bigskip}
&&&\phantom{30000}eof\cr
\noalign{\bigskip}
&&&6\cr
&&&\phantom{6000}$+$\cr}}$$

\bigskip
The above program can be abbreviated, by leaving out the terminal states,
marking the nonterminal states from which eof leads to an accepting state,
and omitting the word ``scan'':

\bigskip
$$\vcenter{\halign{\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\cr
&&&&&&&&$b$\cr
\noalign{\bigskip}
&&&&$a$\cr
$\Rightarrow$&1&&&&&&2\cr
&&&$b$&&$b$\cr
&&$a$&&&&$a$\cr
\noalign{\bigskip}
&&&&3\cr}}$$

\bigskip
\noindent
This is the traditional graphic picture of a finite acceptor.


\bigskip
\parindent0pt
\copyright 1988 Robert W. Floyd

First draft April 12, 1988.

\bye